Chapter 50: Thinking Logically, Thinking Concurrently

Structured programming aims to improve clarity and maintainability; through sequences, selection or iteration. Flowcharts and pseudocode (for more complex algorithms) are used to design algorithms. For testing, trace tables are followed through manually.

Concurrent and parallel computing are considered to be related but distinct, and have debatable differences.

Concurrent: when multiple processes are running, each in turn given a slice of processor time; mimics multitasking with a single processor.

Increases rate of tasks completed;

No wasted time waiting user data input; used for another task;

However, if many users try to run heavy computation requiring programs they will take longer to complete.

Parallel: multiple processors are required to execute different instructions simultaneously; speeds up computations - impossible on single processor.

Different processors enable several tasks to be performed; speed up repetitive calculations on large amounts of data;

GPU quickly renders 3D object; works individual parts simultaneously;

Browser displaying several web pages and queries being performed in different pages;

However, some tasks may run faster with single processor.

Chapter 51: Problem Recognition

Problems are computable if they are solvable by an algorithm. If they take millions of years to solve, they are considered to be practically insoluble.

Problem Solving Methods

1. Enumeration: exhaustive search by listing all cases, can be inefficient.
2. Simulation: creating a model of a real system to understand its behaviour and evaluate strategies for operation. Examples are financial risk analysis, population predictions, queueing problems, etc.
3. Divide and conquer: reduces size of problem each iteration; reduces time of solving problem for some tasks, not all.
4. Problem abstraction: removing details and making problems easier to solve as reduced to one that has already been solved.

Automation

Building models and putting them into action to solve problems. Needs to decide what needs to be included and what assumptions are being made. Automating abstractions tells us more about the reality of what we are modelling.

Chapter 52: Problem Solving

The manner you present a problem is important to find the solution: this is visualisation

Backtracking: methodical way of trying out different sequences until you find one that leads to a solution.

In some problems you need to make a series of decisions but there are cases which:

You don’t have enough info to know which is the best choice;

Each decision leads to a new set of choices

One or more of the sequences may be a solution to the problem

Data Mining: process of digging through big data (large data sets that cannot be easily handled in a traditional database) sets to discover hidden connections and predict future trends.

Intractable problems: problems that have an algorithm that solves them would take an unreasonably long time for even a fast computer to find the solution to solve through brute force. Not all of these problems are equally as hard.

Heuristic approach: problem solving which employs an algorithm or methodology to give an adequate solution in a reasonable time. It trades optimality, completeness, accuracy or precision for speed.

Performance modelling: process of simulating different user and system loads on a computer using mathematical approximation, rather than doing actual performance testing which may be difficult and expensive. Outputs may be used to help with planning a new system.

Pipelining: technique of splitting tasks into smaller parts and overlapping the processing of each part of the task. While one instruction is fetched, another is decoded and a third is executed.